package solution;

import common.Node;

import java.util.LinkedList;
import java.util.Stack;

import static jdk.nashorn.internal.objects.NativeArray.reverse;

/**
 * create by yongli on 2020-07-21 23:16
 * 实现链表的反转功能
 */

public class LinkListReverse {

    // 测试方法
    public static void main2(String[] args) {
        // 系统自定义的LinkedList，没有next方法
        LinkedList<Integer> integers = new LinkedList<>();
        integers.add(1);
        integers.add(2);
        integers.add(3);
        System.out.println(reverse(integers));
    }

    public static void main(String[] args){
        Node<Integer> header =new Node<>(12);
        Node<Integer> cur = header;
        for(int i=0;i<3;i++){
            Node<Integer> node = new Node<>(i+1);
            // 改变原有链表
            cur.next =node;
            cur = cur.next;
        }
        travel(header);
        travel(reverse(header));
    }

    public static void travel(Node<Integer> header){
        Node<Integer> cur =header;
        while(cur!=null){
            System.out.println(cur.item);
            cur = cur.next;
        }
    }

    // 当然，一般也可以使用递归的方法。
    // 递归调用了多少此，函数就返回了多少此，最终结果是最外层的值
    public static Node<Integer>  reverse2(Node<Integer> header){
        if(header==null && header.next==null){
            return header;
        }else {
           Node<Integer> last= reverse2(header.next);
        Node<Integer> end = header.next;
        end.next = header;
        header.next =null;
        // last是最后节点
        return last;
    }

    // 调整指针的转向 pre--> cur  ==>  pre<-cur
    // 一要调整，二要返回
    public static Node<Integer> reverse(Node<Integer> header){
        Node<Integer> pre =header;
        Node<Integer> cur = header.next;
        header.next = null;
        while (cur!=null){
            Node<Integer> temp = cur.next;
            // 调整
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    public static void travel2(Node<Integer> header){
        if(header==null){
            return;
        }
        // 如果子节点存在，则进入子节点
        if(header.next!=null){
            travel2(header.next);
        }
        // 后遍历
        System.out.println(header.item);
    }

    public static <T> LinkedList<T> reverse(LinkedList<T> linkedList){
        Stack<T> stack = new Stack<>();
        // 倒一下
        for(T e:linkedList){
            stack.push(e);
        }
        LinkedList<T> res = new LinkedList<>();
        while (!stack.isEmpty()){
            res.add(stack.pop());
        }
        return res;
    }
}
